public class BinarySearchTree {
    //二叉搜索树
    static class   TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    public TreeNode root=null;
    //查找二叉搜索树中指定的val值
    public TreeNode find(int val){
        TreeNode cur=root;
        while(cur!=null){
            if (cur.val==val){
                return cur;
            } else if (val>cur.val) {
                cur=cur.right;
            }else {
                cur=cur.left;
            }
        }
        return null;
    }
    //插入一个数据
    public void insert(int val){
        if (root==null){
            root=new TreeNode(val);
            return ;
        }
        TreeNode cur=root;
        TreeNode parent=null;
        while (cur!=null){
            parent=cur;
            if (val<cur.val){
                cur=cur.left;
            } else if (val> cur.val) {
                cur=cur.right;
            }else {
                return;
            }
        }
        if (val< parent.val){
            parent.left=new TreeNode(val);
        } else if (val> parent.val) {
            parent.right=new TreeNode(val);
        }

    }
    //中序遍历
    public void inorder(TreeNode root){
        if (root==null){
            return ;
        }
        inorder(root.left);
        System.out.println(root.val+" ");
        inorder(root.right);
    }
    //删除某个节点
    public void remove(int val){
        TreeNode cur=root;
        TreeNode parent=null;
        while (cur!=null){
            if (cur.val==val){//找到要删除的值
                removeNode(parent,cur);
                return;
            } else if (cur.val<val) {
                parent=cur;
                cur=cur.right;
            }else {
                parent=cur;
                cur=cur.left;
            }
        }
    }

    private void removeNode(TreeNode parent, TreeNode cur) {
        if (cur.left==null){
            if (cur==root){
                root=cur.right;
            }else if (parent.left==cur){
                parent.left=cur.right;
            }else{
                parent.right=cur.right;
            }
        }else if (cur.right==null){
            if (cur==root){
                root=cur.left;
            } else if (cur == parent.left) {
                parent.left=cur.left;
            }else {
                parent.right=cur.left;
            }
        }else {
            TreeNode targetP=cur;
            TreeNode target=cur.right;
            while (target.left!=null){
                targetP=target;
                target=target.left;
            }
            //走到这里意味着target.left==null
            //如果target往下，右子树中存在左子树，在右子树的左子树中找到最小值，用该值替换cur.val
            cur.val=target.val;
            if (target==targetP.left){
                targetP.left=target.right;
            }else{//如果target往下，无左子树，此时cur的值已经为target的值
                //把target右边连接到targetP的右边
                targetP.right=target.right;//相当于删除target
                //此时的右子树的值一定都大于cur的值
            }
        }
    }
}
